package cumt.oj;

/**
 * @Author Fizz Pu
 * @Date 2020/11/17 下午2:59
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.util.*;

/**
 * 题目描述
 *         给定一只含有小写字母的字符串；输出其哈夫曼编码的长度
 *
 *         输入
 *         第一行一个整数T，代表样例的个数，接下来T行，每行一个字符串，0<T<=2000,字符串长度0<L<=1500.
 *
 *         输出
 *         对于每个字符串，输出其哈夫曼编码长度
 *
 *         样例输入
 *         3
 *         hrvsh
 *         lcxeasexdphiopd
 *         mntflolfbtbpplahqolqykrqdnwdoq
 *         样例输出
 *         10
 *         51
 *         115
*/

// 这个问题可以先利用优先级队列构建一颗huffman树,
// 然后利用树来求长度,这样的话,
// 牵涉到一个问题, 要求从根节点到各个叶子节点的高度, 这样的解决方案肯定不行
// 是否可以记录下他的长度9
// 我想了一种解决方案, 每个节点加一个属性, 保存他们的叶子节点到当前节点的高度, 用什么数据结构存,当然用map了,
// key为叶子节点node,value高度
// 最后算根节点就可以了
// 这算是自己想的东西了, 果然树这东西可扩展性很高啊!


class Node implements Comparable<Node>{
    int count;
    Map<Character, Integer> node;

    public Node(Map.Entry<Character, Integer> entry) {
        this.count = entry.getValue();
        node = new HashMap<>();
        node.put(entry.getKey(), 0);
    }

    @Override
    public int compareTo(Node ob){
        return this.count - ob.count;
    }

    public void setCount(int count) {
        this.count = count;
    }

    public void setNode(Map<Character, Integer> node) {
        this.node = node;
    }
}


public class HaffMan {

    static void help(Map<Character, Integer> map){
        for(Map.Entry<Character, Integer> entry : map.entrySet()){
            map.put(entry.getKey(), entry.getValue()+1);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        String str = null;
        for(int i = 0; i < N; ++i) {
            str = scanner.next();

            // 统计频次
            Map<Character, Integer> map = new HashMap<>();
            char ch;
            for (int j = 0; j < str.length(); ++j) {
                ch = str.charAt(j);
                if(!map.containsKey(ch))map.put(ch, 1);
                else map.put(ch, map.get(ch) + 1);
            }

            // 首先全部入队
            PriorityQueue<Node> priorityQueue = new PriorityQueue<>();
            for(Map.Entry<Character, Integer> entry : map.entrySet()){
                priorityQueue.add(new Node(entry));
            }

            while (priorityQueue.size() > 1) {
                Node node1 = priorityQueue.remove();
                Node node2 = priorityQueue.remove();
                node1.setCount(node1.count + node2.count); // 丢弃node2
                // node1.node.replaceAll((k, v) -> node1.node.get(k) + 1);
                // node2.node.replaceAll((k, v) -> node2.node.get(k) + 1);
                help(node1.node);
                help(node2.node);
                node1.node.putAll(node2.node);
                priorityQueue.add(node1);
            }

            Node res =  priorityQueue.remove();

            int sums = 0;
            for(Map.Entry<Character, Integer> entry: res.node.entrySet()){
                int count = map.get(entry.getKey());
                sums += entry.getValue() * count;
            }

            System.out.println(sums);
        }
    }
}
